package BackTrackingPackage;


import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author Lzm
 * @version 1.0
 */
/*n皇后问题, 难点:终止条件 和 判断放置皇后位置是否合法*/
public class solveNQueens_ {
  LinkedList<String> list = new LinkedList<>();
  List<List<String>> result = new ArrayList<>();
  @Test
  public void solveNQueenTest(){
    int n = 4;
    char[][] chessboard = new char[n][n];
    for (int i = 0 ; i < n ; i ++){
      Arrays.fill(chessboard[i],'.');
    }
    //System.out.println(Array2List(chessboard));
    backTracking(n,chessboard,0);
    System.out.println(result);
  }
  public void backTracking(int n,char[][]chessboard,int row){
      if (row == n){
        result.add(Array2List(chessboard));
        return;
      }
      for (int i = 0 ; i < n ; i++){
        if (isValid(row,i,chessboard,n)){
          chessboard[row][i] = 'Q';
          backTracking(n,chessboard,row + 1);
          /*回溯*/
          chessboard[row][i] = '.';
        }
      }
  }
  /*判断chessboard棋盘上在row行,i列放置皇后是否合法*/
  public boolean isValid(int row,int col,char[][]chessboard,int n){
    for (int i = 0 ; i < n - col ; i++){
      if (chessboard[row][i] == 'Q'){
        return false;
      }
    }
      for (int i = 0 ; i < row ; i++){
        if (chessboard[i][col] == 'Q'){
          return false;
        }
      }
      //检查45°
      for (int i = row - 1 , j = col + 1 ; i >= 0 && j <= n - 1 ; i-- ,j++){
        if (chessboard[i][j] == 'Q'){
          return false;
        }
      }
    //检查135°
    for (int i = row - 1 , j = col - 1 ; i >= 0 && j >= 0 ; i-- ,j--){
      if (chessboard[i][j] == 'Q'){
        return false;
      }
    }
      return true;
  }
  public static List Array2List(char[][] chessboard) {
    List<String> list = new ArrayList<>();
    StringBuilder stringBuilder = new StringBuilder();
    for (int i = 0 ; i < chessboard.length ; i++){
      stringBuilder.append("\"");
      for (char c : chessboard[i]) {
        stringBuilder.append(c);
      }
      if (i != chessboard.length - 1){
        stringBuilder.append("\"").append(",");
      }
    }
    stringBuilder.append("\"");
    list.add(stringBuilder.toString());
    return list;
  }
}
